package cn.z2huo.leetcode.problem.NO_0002;

/**
 * <p>给定两个非空链表来表示两个非负整数。位数按照逆序方式存储，它们的每个节点只存储单个数字。
 * <p>将两数相加返回一个新的链表。
 * <p>你可以假设除了数字 0 之外，这两个数字都不会以零开头。
 *
 * <p>示例：
 *
 * <p>输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
 * <p>输出：7 -> 0 -> 8
 * <p>原因：342 + 465 = 807
 *
 * @author z2huo
 */
class Solution {

    /**
     * <p>链表中的第一个元素为个位元素，第二个为10位元素，第三个元素为百位元素
     * <p>分别计算两个链表的数值，然后相加
     *
     * <p>这个方法当时对题目的理解是错误的，对题目要求的输出结果的理解也是错误的
     * <p>题目要求输出结果为一个链表，链表中的各个节点代表的是整数各个位置的值，而不是数字本身
     *
     * @param l1 链表 1
     * @param l2 链表 2
     * @return 两个链表中数的和代表的链表
     */
    @Deprecated
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {

        // 第一个链表中所有数字代表的值
        int num = 0;
        // 第二个链表中所有数字代表的值
        int num2 = 0;
        // 链表中数字的位数
        int digit = 0;

        while (l1 != null) {
            num += (int) (l1.val * Math.pow(10, digit));
            l1 = l1.next;
            digit++;
        }

        digit = 0;
        while (l2 != null) {
            num2 += (int) (l2.val * Math.pow(10, digit));
            l2 = l2.next;
            digit++;
        }

        // 最后这个是错误的！！！
        // 返回值不应该是链表的一个节点，应该是一个链表，链表中各个节点表示的使非负整数结果中各个位置的值
        return new ListNode(num + num2);
    }

    /**
     * <p>仿照两数相加，从个位加到百位
     * <p>链表中的各个位置的值为 0 到 9
     *
     * @param l1 链表 1
     * @param l2 链表 2
     * @return 两个链表中数的和代表的链表
     */
    public ListNode addTwoNumbers2(ListNode l1, ListNode l2) {
        ListNode resultNode = new ListNode();
        ListNode tempNode = resultNode;

        while (l1 != null || l2 != null) {
            // 判断两个输入链表中当前节点的值
            int num = l1 == null ? 0 : l1.val;
            int num2 = l2 == null ? 0 : l2.val;

            int sum = num + num2 + tempNode.val;
            // 计算结果链表中当前节点的值
            tempNode.val = sum % 10;

            if (l1 != null) {
                l1 = l1.next;
            }
            if (l2 != null) {
                l2 = l2.next;
            }
            if (l1 != null || l2 != null || sum >= 10) {
                // 结果链表当前节点的 next 新建并赋值，赋值为当前节点计算的商
                tempNode.next = new ListNode(sum / 10);
                tempNode = tempNode.next;
            }
        }
        return resultNode;
    }

    /**
     * <p>{@link Solution#addTwoNumbers2(ListNode, ListNode)} 方法，删除多余变量，节省消耗内存
     *
     * @param l1 输入链表
     * @param l2 输入链表
     * @return 结果链表
     */
    public ListNode addTwoNumbers2deleteRedundantVar(ListNode l1, ListNode l2) {
        ListNode resultNode = new ListNode();
        ListNode tempNode = resultNode;

        while (l1 != null || l2 != null) {
            // 判断两个输入链表中当前节点的值

            int sum = (l1 == null ? 0 : l1.val) + (l2 == null ? 0 : l2.val) + tempNode.val;
            // 计算结果链表中当前节点的值
            tempNode.val = sum % 10;

            if (l1 != null) {
                l1 = l1.next;
            }
            if (l2 != null) {
                l2 = l2.next;
            }
            if (l1 != null || l2 != null || sum >= 10) {
                // 结果链表当前节点的 next 新建并赋值，赋值为当前节点计算的商
                tempNode.next = new ListNode(sum / 10);
                tempNode = tempNode.next;
            }
        }
        return resultNode;
    }

    /**
     * @param l1 输入链表
     * @param l2 输入链表
     * @return 结果链表
     */
    public ListNode addTwoNumbers3(ListNode l1, ListNode l2) {
        ListNode result = new ListNode(0);
        ListNode temp = result;

        // 这个值用来存储结果链表中当前留给下一个节点的商
        int tempNum = 0;
        while (l1 != null || l2 != null) {
            int num = l1 == null ? 0 : l1.val;
            int num2 = l2 == null ? 0 : l2.val;

            int sum = num + num2 + tempNum;
            tempNum = sum / 10;
            temp.next = new ListNode(sum % 10);
            temp = temp.next;

            if (l1 != null) {
                l1 = l1.next;
            }
            if (l2 != null) {
                l2 = l2.next;
            }
        }
        // 判断是否还有下一个节点
        if (tempNum > 0) {
            temp.next = new ListNode(tempNum);
        }
        return result.next;
    }

    /**
     * <p>递归实现
     *
     * <p>边界条件为入参的两个链表往后没有元素了
     * <p>递归过程为 构造新节点
     *
     * @param l1 输入链表
     * @param l2 输入链表
     * @return 结果链表
     */
    public ListNode addTwoNumbersRecursion(ListNode l1, ListNode l2) {

        // 如果两个链表的节点存在 null 的话，则不需要相加了，直接返回另一个链表的节点
        if (l1 == null) {
            return l2;
        }
        if (l2 == null) {
            return l1;
        }

        // 两个链表节点的和
        int sum = l1.val + l2.val;
        // 当前节点为两个链表节点和取余
        ListNode resultNode = new ListNode(sum % 10);
        // 下一个节点由两个链表节点的下一个节点来计算
        resultNode.next = addTwoNumbersRecursion(l1.next, l2.next);
        // 如果和大于 10，需要将十位上的数值进到下一位
        // 由因为本题目的前提条件是入参链表节点的 值 >= 0 && 值 <= 9，所以和最大为 18 最小为 0，所以只用判断是否大于 10 即可
        if (sum >= 10) {
            // 和大于 10，则需要进位，需要在当前节点的下一个节点上再加 1，所以需要重新获取 resultNode.next
            // 入参中，第一个参数为之前的计算结果，第二个参数为需要进位的 1
            resultNode.next = addTwoNumbersRecursion(resultNode.next, new ListNode(1));
        }
        return resultNode;
    }
}
